#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 85;
const int K = 8;
int n, k, q;
int c[N][N];
ll f[N][1 << K], g[N][1 << K];
int used[N];
ll ans[N][N];
void init_f() {
  memset(f, 0x3f, sizeof(f));
  rep(i, 0, k - 1) f[i][1 << i] = 0;
  rep(s, 1, (1 << k) - 1) {
    rep(i, 0, n - 1) {
      for (int t = (s - 1) & s; t; t = (t - 1) & s) {
        f[i][s] = min(f[i][s], f[i][t] + f[i][s ^ t]);
      }
    }
    rep(i, 0, n - 1) used[i] = 0;
    rep(i, 1, n - 1) {
      int v = -1;
      rep(j, 0, n - 1) {
        if (!used[j] && (v == -1 || f[j][s] < f[v][s])) v = j;
      }
      used[v] = 1;
      rep(j, 0, n - 1) { f[j][s] = min(f[j][s], f[v][s] + c[v][j]); }
    }
  }
}
void init_g() {
  // g[i][s] == f[i][s ^ (1 << u)]
  rep(u, k, n - 1) {
    memset(g, 0x3f, sizeof(g));
    g[u][0] = 0;
    rep(s, 0, (1 << k) - 1) {
      rep(i, 0, n - 1) {
        for (int t = s; t; t = (t - 1) & s) {
          g[i][s] = min(g[i][s], g[i][s - t] + f[i][t]);
        }
      }
      rep(i, 0, n - 1) used[i] = 0;
      rep(i, 1, n - 1) {
        int v = -1;
        rep(j, 0, n - 1) {
          if (!used[j] && (v == -1 || g[j][s] < g[v][s])) v = j;
        }
        used[v] = 1;
        rep(j, 0, n - 1) g[j][s] = min(g[j][s], g[v][s] + c[v][j]);
      }
    }
    rep(v, k, n - 1) ans[u][v] = g[v][(1 << k) - 1];
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  rep(i, 0, n - 1) rep(j, 0, n - 1) cin >> c[i][j];
  init_f();
  init_g();
  cin >> q;
  while (q--) {
    int s, t;
    cin >> s >> t;
    cout << ans[s - 1][t - 1] << endl;
  }
  return 0;
}